package 力扣;

import sun.reflect.generics.tree.Tree;

import java.util.Arrays;

/**
 * @author yyq
 * @create 2022-04-14 9:59
 */
public class leetcode654 {
    public static void main(String[] args) {
        constructMaximumBinaryTree(new int[]{3,2,1,6,0,5});
    }
    public static TreeNode constructMaximumBinaryTree(int[] nums) {
        int maxIndex = getMaxIndex(nums,0,nums.length-1);
        TreeNode root = new TreeNode(nums[maxIndex]);
        int rootleft0 = -1;
        int rootleft1 = -1;
        int rootright0 = -1;
        int rootright1 = -1;
        if(maxIndex>0){
            rootleft0 = 0;
            rootleft1 = maxIndex-1;
        }
        if(maxIndex<nums.length-1){
            rootright0 = maxIndex+1;
            rootright1 = nums.length-1;
        }

        constructToTree(root,nums,rootleft0,rootleft1,rootright0,rootright1);
        return root;
    }

    private static void constructToTree(TreeNode root, int[] nums, int rootleft0, int rootleft1, int rootright0, int rootright1) {
        if(rootleft0==-1&&rootright0==-1) return;
        TreeNode left = null;
        TreeNode right = null;
        if(rootleft0!=-1){
            int leftMaxIndex = getMaxIndex(nums, rootleft0, rootleft1);
            left = new TreeNode(nums[leftMaxIndex]);
            root.left = left;

            int hasleft = 1;
            int hasright = 1;
            if(leftMaxIndex ==rootleft0) hasleft=0;
            if(leftMaxIndex ==rootleft1) hasright =0;
            // 有左右子树
            if(hasleft==1&&hasright==1){
                constructToTree(root.left,nums,rootleft0,leftMaxIndex-1,leftMaxIndex+1,rootleft1);
            }
            // 只有左子树
            if(hasleft==1&&hasright==0){
                constructToTree(root.left,nums,rootleft0,leftMaxIndex-1,-1,-1);
            }
            // 只有右子树
            if(hasleft==0&&hasright==1) {
                constructToTree(root.left,nums,-1,-1,leftMaxIndex+1,rootleft1);
            }
            //既没有左子树又没有右子树 不需要操作

        }
        if(rootright0!=-1){
            int rightMaxIndex = getMaxIndex(nums, rootright0, rootright1);
            right = new TreeNode(nums[rightMaxIndex]);
            root.right = right;

            int hasleft = 1;
            int hasright = 1;
            if(rightMaxIndex ==rootright0) hasleft=0;
            if(rightMaxIndex ==rootright1) hasright =0;
            // 有左右子树
            if(hasleft==1&&hasright==1){
                constructToTree(root.right,nums,rootright0,rightMaxIndex-1,rightMaxIndex+1,rootright1);
            }
            // 只有左子树
            if(hasleft==1&&hasright==0){
                constructToTree(root.right,nums,rootright0,rightMaxIndex-1,-1,-1);
            }
            // 只有右子树
            if(hasleft==0&&hasright==1) {
                constructToTree(root.right,nums,-1,-1,rightMaxIndex+1,rootright1);
            }
            //既没有左子树又没有右子树 不需要操作
        }

                                                                                                                                          
    }

    public static int getMaxIndex(int[] nums,int left,int right){
        int max = nums[left];
        int index = left;
        for (int i = left; i<=right;i++){
            if(nums[i]>max) {
                max = nums[i];
                index = i;
            }
        }
        return index;
    }
}
